1. Field of the Invention
The present invention relates to computer architectures. More specifically, the present invention relates to reconfigurable computer architectures.
2. Description of the Related Art
Most processing applications are currently performed using a software implementation on a fixed hardware architecture, which is designed to execute a particular class of software. Alternatively, many applications may be implemented by designing hardware to execute only the algorithms required. Such dedicated hardware can typically execute a given algorithm 2-3 orders of magnitude more efficiently than software, in terms of speed, power, and size. Unfortunately, dedicated hardware is inflexible and cannot easily be changed to perform functions other than those for which it was originally designed. Accordingly, reconfigurable computers have been developed as a compromise between the processing efficiencies afforded by dedicated hardware and the flexibility afforded by software.
The reconfigurable computer (RC) is a digital device whose internal circuits may be programmably re-wired in order to implement various functions. Because the desired functions are directly implemented in logic, the RC can be 10 to 100 times more efficient (in speed, power, and density) than conventional general-purpose computers. A problem with the RC is that programming can be difficult and limited in flexibility.
In the prior art, there have been a number of variations on the RC to enhance capability and programming. First, there was an evolution from fine-grained logic elements (i.e., gates) to coarse-grained functional elements (i.e., arithmetic functions). Second, route timing between elements was made deterministic, independent of program. Third, data flow architectures provided automatic alignment of operands. However, what are needed are better methods for dynamic decision making during processing.
A reconfigurable computer typically includes a multiplicity of operational elements (such as arithmetic/logic units, processors, memory, etc.) and a programmable interconnection network for connecting the elements in accordance with user-defined configuration settings.
An important type of RC uses a distributed control, data flow architecture. In accordance with conventional teachings, the data flow control logic is restricted to a single type of logical function. That is, an element performs an operation if and only if all selected input sources are available and all selected output sources are available. This type of control system works well for many applications, but there are some applications that could be more advantageously implemented using different forms of data flow control. An example application is where there are multiple data sources and it is desirable to operate on the first data signal that appears. In this case, it would be more efficient to have the data flow logic to be such that the element performs an operation if any selected input source is available (and all the selected output sources are available).
Hence, a need exists in the art for an improved data flow control logic for reconfigurable computers offering more flexibility than conventional approaches.
Further, for many applications it is necessary to have another degree of control. That is, the ability to dynamically switch the RC interconnection network on a sample-by-sample basis, responsive to the control bits and control states that occur at each sample. In accordance with conventional teachings, dynamic switching may be accomplished by making the programmable interconnect network to be dynamic. This has the disadvantage that a large, dynamically switched network is complex and costly to implement, in terms of chip size, power, and speed. (Since an RC should have a large number of elements, the interconnection network is necessarily large and thus difficult for a completely dynamic implementation.)
Alternatively, conventional teaching provides that the interconnection network be static, and that dynamic switching be done by individual elements, in addition to their primary operations. For example, an arithmetic logic unit (ALU) functional element may include a dynamic switch at its input, selecting any of 4 input ports as its two input operands. Thus dynamic switching of operand sources can be done from a limited selection. Also, by using the ALU pass-through modes, a standalone, 4 to 1 multiplex switch can be configured. This approach has the disadvantage of inefficiency: all of the functional elements carry the overhead of switching, even though only a few would typically be used for dynamic switching. (The inefficiency is manifest primarily in the interconnection network, because there are now many more ports to be connected.) Another disadvantage is that in order to configure various types of dynamic switching, many functional elements may be needed, and they are thus unavailable for their primary function. As an example, to build a 4×4 dynamic crossbar would use four of the aforementioned ALU elements, devoted solely to switching.
Therefore, a need exists in the art for an improved method for providing dynamic switching in reconfigurable computers that is more efficient than conventional approaches.